题目描述长度为n但是不含11的字符串(只含01构成)有多少？（允许有前导0) 输入一个正整数长度n$(1<=n<=1000)$ 输出所有不含有11的字符串的总数由于数值很大，请输出对与$1000000007$取模的结果 样例输入12 样例输出13 题解1234567891011121314151617#include <iostream>#include <cstring>using namespace std;int main() { int n; cin >> n; long long dp[1001][2]; memset(dp, 0, sizeof(dp)); dp[1][0] = 1; dp[1][1] = 1; for (int i = 2; i <= n; i++) { dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % 1000000007; dp[i][1] = ...

题目描述有一些装有铀(用U表示)和铅(用L表示)的盒子，数量均足够多。要求把N个盒子放成一行，但至少有3个U放在一起，有多少种方法？ 输入第一行包含一个整数N $(3<=N<=1000000)$。 输出输出一个整数表示方法数(结果模 $1000000007$ )。 样例输入14 样例输出13 提示$$3<=N<=30$$ 输入：4 输出：3 样例解释：UUUL、LUUU、UUUU 题解12345678910111213141516171819#include<iostream>using namespace std;int main() { long long dp[1000001][4]; int mod = 1000000007; int n; while (cin >> n) { dp[0][0] = dp[0][1] = 1; dp[0][2] = dp[0][3] = 0; for (int...

题目描述平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。 输入输入数据包含多个测试实例,每个测试实例占一行,每行包含一个正整数n（n<=20）,n表示直线的数量. 输出每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数,每行的整数之间用一个空格隔开。 样例输入1223 样例输出120 10 2 3 题解123456789101112131415161718192021#include<iostream>#include <cstring>using namespace std;int main() { int dp[21][200]; int n; memset(dp, 0, sizeof(dp)); for (int i = 0; i < 21; i++) { dp[i][0] = 1; for (int j = 0; j <= i * ...

题目描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天， 雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截    所有的导弹。输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数)，计算这套系统最多能拦截多少导弹。 输入多组输入。 第一行为一个整数n，表示接下来有n个整数 第二行，包括若干以空格分隔的正整数，表示来袭的导弹的高度。 输出只有一个正整数,表示最多能拦截的导弹数。 样例输入128389 207 155 300 299 170 158 65 样例输出16 题解1234567891011121314151617#include<iostream>#include <algorithm>using namespace std;int main() { int tmp[10001], arr[10001], n; while (cin >> ...

题目描述设矩阵A为$100×1$的矩阵，B为$1×100$矩阵，C为$100×1$的矩阵，则计算$A×B$的时间耗费为$10000$（由$100×1×100$得到），得到的结果D为$100×100$矩阵，再与C相乘所需的时间耗费为$1000000$，因此计算$(A×B)×C$的总时间$1010000$。$B×C$的时间耗费为$10000$，得到的中间矩阵为$1×1$矩阵，再与Ａ相乘的时间耗费为$100$，因而计算$A×(B×C)$的时间耗费只有$10100$。从上面的分析可以看的出不同的乘法顺序所耗费的时间是不同，甚至是相差很大的。现有一矩阵链$M1×M2×M3×M4×M5×M6………$，试问如何选择计算顺序才能使所耗费的时间最少。 输入矩阵乘法链长度为N的问题其输入数据由$N＋1$行组成，第一行为矩阵乘法链的长度，即矩阵的个数。剩下的N行为N个矩阵的行列信息。每行的第一个元素是矩阵行数，第二个元素是矩阵的列数，元素之间以空格隔开。 输出输出计算这个矩阵乘法链的最少耗费时间。 样例输入1234567630 3535 1515 55 1010 20 20 25 样例输出11512...

题目描述给定一整型数列${a1,a2…,an}$，找出连续非空子串${ax,ax+1,…,ay}$，使得该子序列的和最大，其中,$1<=x<=y<=n$。 输入第一行是一个整数$N$ $(N<=10)$表示测试数据的组数每组测试数据的第一行是一个整数n表示序列中共有n个整数，随后的一行里有n个整数$I$ $(-1000=I<=1000)$，表示数列中的所有元素。$(0<n<=100)$ 输出对于每组测试数据输出和最大的连续子串的和。 样例输入123151 2 -1 3 -2 样例输出15 题解12345678910111213141516171819202122#include <iostream>#include <algorithm>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(n...

题目描述在质数的大家庭中，大小之差不超过2的两个质数称它俩为一对孪生素数，如2和3、3和5、17和19等等。请你统计一下，在不大于自然数N的质数中，孪生素数的对数。 输入只有一行，一个自然数$N$ $(N<=10^6)$ 输出只有一行，一个整数，表示N以内孪生素数的对数。 样例输入120 样例输出15 题解1234567891011121314151617181920#include <iostream>#include <algorithm>using namespace std;const int maxn = 1e6+100;bool p[maxn];void Fill(){ for(bool & i : p)i=true; p[0]=p[1]=false; for(long long i=2;i*i<=maxn;i++)if(p[i])for(long long j=2*i;j<maxn;j+=i)p[j]=0;}int main() { int n; ...

题目描述已知一个数组，说这个数组中的一个平台（Plateau），就是连续的一串值相同的元素，并且这一串元素不能再延伸。例如，在 1，2，2，3，3，3，4，5，5，6 中 1，2,2，3,3,3，4， 5,5，6 都是平台。试编写一个程序，接收一个数组，把这个数组中最长的平台找出来。在上面的例子中 3,3,3 是该数组中最长的平台。（注：为了 方便，测试用例的数组最大长度都不超过 100，数组中的元素全部为整数范围为[-2^31,2^31-1]）。 输入多组测试数据,处理到文件结尾。每组数据首先由一个数组的长度 L，随后跟随 L 个该数组数据组成。 输出对于每个测试用例输出它的最长平台 样例输入123456101 2 2 3 3 3 4 5 5 6111 1 1 1 1 1 2 2 2 2 251 2 3 4 5 样例输出123361 题解123456789101112131415161718#include <iostream>#include <algorithm>using namespace std;int main(){ in...

题目描述假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。（这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。） 算法设计：对于给定的 k 个待安排的活动，计算使用最少会场的时间表。 输入输入第一行有 1 个正整数 k，表示有 k 个待安排的活动。接下来的 k 行中，每行有 2 个正整数，分别表示 k 个待安排的活动开始时间和结束时间。时间以 0 点开始的分钟计。 输出将计算出的最少会场数输出 样例输入12345651 2312 2825 3527 8036 50 样例输出13 题解12345678910111213141516171819202122#include <iostream>#include <algorithm>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); c...

题目描述对于一个给定的长度为N的整数序列A，它的“子序列”的定义是：A中非空的一段连续的元素（整数）。你要完成的任务是，在所有可能的子序列中，找到一个子序列，该子序列中所有元素的和是最大的（跟其他所有子序列相比）。程序要求你输出这个最大值。 输入输入文件的第一行包含一个整数N，第二行包含N个整数，表示A。其中 $$1<=N<=100000$$$$-10000<=A[i]<=10000$$ 输出输出仅包含一个整数，表示你算出的答案。  样例输入125 3 -2 3 -5 4 样例输出14 提示$O(nlogn)$ $O(n)$可以过 题解1234567891011121314151617181920#include <cstdio>int main() { int n, a[100001]; while (~scanf("%d", &n)) { int i; for (i = 1; i <= n; i...